{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Average Subarray I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findMaxAverage"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子数组最大平均数 I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由 <code>n</code> 个元素组成的整数数组 <code>nums</code> 和一个整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>请你找出平均数最大且 <strong>长度为 <code>k</code></strong> 的连续子数组，并输出该最大平均数。</p>\n",
    "\n",
    "<p>任何误差小于 <code>10<sup>-5</sup></code> 的答案都将被视为正确答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,12,-5,-6,50,3], k = 4\n",
    "<strong>输出：</strong>12.75\n",
    "<strong>解释：</strong>最大平均数 (12-5-6+50)/4 = 51/4 = 12.75\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [5], k = 1\n",
    "<strong>输出：</strong>5.00000\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-average-subarray-i](https://leetcode.cn/problems/maximum-average-subarray-i/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-average-subarray-i](https://leetcode.cn/problems/maximum-average-subarray-i/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,12,-5,-6,50,3]\\n4', '[5]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        size = len(nums)\n",
    "        res = -float('inf')\n",
    "        total = 0\n",
    "        res = -float('inf')\n",
    "        for index, n in enumerate(nums):\n",
    "            if index <= k - 1:\n",
    "                total += n\n",
    "                if index == k - 1:\n",
    "                    res = max(total/k, res)\n",
    "            else:\n",
    "                total = total-nums[index-k] + nums[index]\n",
    "                res = max(total/k, res)\n",
    "  \n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        l = len(nums)\n",
    "        if k == 1: return max(nums)\n",
    "        if k== l:  return sum(nums) / k\n",
    "        sums = maxs = sum(nums[0:k]) # 0 1 2 \n",
    "        for i in range(k,l):\n",
    "            sums = sums + nums[i] - nums[i-k]\n",
    "            maxs = max(sums,maxs)\n",
    "                \n",
    "        return maxs/k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        res = sum(nums[0:k])\n",
    "        temp = res;\n",
    "        n = len(nums)\n",
    "        for i in range(k,n):\n",
    "            res = res - nums[i-k] + nums[i]\n",
    "            temp = max(temp,res)\n",
    "            \n",
    "        return temp/(k+0.0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        min_nums = 0\n",
    "        pre_sum = 0\n",
    "        for j in range(k):\n",
    "            min_nums+=nums[j]\n",
    "        \n",
    "        pre_sum = min_nums\n",
    "        \n",
    "        for i in range(k,len(nums)):\n",
    "            \n",
    "            now = pre_sum + nums[i] - nums[i-k]\n",
    "            if min_nums <now:\n",
    "                min_nums = now\n",
    "            pre_sum = now\n",
    "            \n",
    "        return min_nums/k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        s = sum(nums[:k])\n",
    "        r = s\n",
    "        for i in range(k, len(nums)):\n",
    "            s += nums[i]\n",
    "            s -= nums[i-k]\n",
    "            r = max(r, s)\n",
    "        return r/k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        nsum = [0]\n",
    "        for num in nums:\n",
    "            nsum.append(nsum[-1]+num)\n",
    "        maxsum = max(nsum[i+k]-nsum[i] for i in range(len(nums)-k+1))\n",
    "        return maxsum/k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: list, k: int) -> float:\n",
    "        window = []\n",
    "        s = float('-inf')\n",
    "        for i in range(len(nums)):\n",
    "            if len(window) < k:\n",
    "                window.append(nums[i])\n",
    "            else:\n",
    "                if nums[i] >= window[0]:\n",
    "                    window.pop(0)\n",
    "                    window.append(nums[i])\n",
    "                else:\n",
    "                    s = max(sum(window) / k, s)\n",
    "                    window = nums[i-k+1:i+1]\n",
    "            if i == len(nums) - 1:\n",
    "                return max(sum(window) / k, s)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: 'List[int]', k: 'int') -> 'float':\n",
    "        \n",
    "        currsum = sum(nums[:k])\n",
    "        maxsum = currsum\n",
    "        \n",
    "        for i in range(0,len(nums)-k):\n",
    "            currsum += nums[i+k] - nums[i]\n",
    "            maxsum = max(currsum,maxsum)\n",
    "        \n",
    "        return maxsum / k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        out=0\n",
    "        res=0\n",
    "        for i in range(k):\n",
    "            res+=nums[i]\n",
    "        out=res\n",
    "        \n",
    "        i=k\n",
    "        while i<len(nums):\n",
    "            res=res+nums[i]-nums[i-k]\n",
    "            out =max(res,out)\n",
    "            i+=1\n",
    "            \n",
    "\n",
    "        return out/(1.00*k)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "\n",
    "        isum, n = 0, len(nums)\n",
    "        for i in range(k):\n",
    "            isum += nums[i]\n",
    "        imax = isum\n",
    "        for i in range(k, n):\n",
    "            isum = isum + nums[i] - nums[i-k]\n",
    "            imax = max(imax, isum)\n",
    "        return float(imax) / k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        sumlist=[]\n",
    "        count=sum(nums[:k:])\n",
    "        if k==1:\n",
    "            return max(nums)\n",
    "        sumlist.append(count)\n",
    "        for i in range(1,len(nums)-k+1):\n",
    "            count=count-nums[i-1]+nums[i+k-1]\n",
    "            sumlist.append(count)\n",
    "        return float(max(sumlist)/k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        count=sum(nums[0:k])\n",
    "        max1=count\n",
    "        for i in range(k,len(nums)):\n",
    "            count=count-nums[i-k]+nums[i]\n",
    "            max1=max(max1,count)\n",
    "        return max1/k\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        N = len(nums)\n",
    "        # 若数组长度小于长度k\n",
    "        if N < k:\n",
    "            return 0\n",
    "        dp = [-123456789] * N\n",
    "        dp[k-1] = sum(nums[:k])\n",
    "        for i in range(k, N):\n",
    "            dp[i] = dp[i - 1] + nums[i] - nums[i - k]\n",
    "        return max(dp) / k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        res = 0\n",
    "        max_res = 0\n",
    "        for i in range(k):\n",
    "            res += nums[i]\n",
    "        print(\"first res is \" + str(res))\n",
    "        left, right = 0, k\n",
    "        max_res = res\n",
    "        while right < len(nums):\n",
    "            res -= nums[left]\n",
    "            res += nums[right]\n",
    "            left += 1\n",
    "            right += 1\n",
    "            print(res)\n",
    "            max_res = max(res, max_res)\n",
    "        return max_res / k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        if k == len(nums): return sum(nums) / k\n",
    "\n",
    "        res = sum(nums[0:k])\n",
    "        s = sum(nums[0:k])\n",
    "        for i in range(k, len(nums)):\n",
    "            s = s - nums[i-k] + nums[i]\n",
    "            res = max(res, s)\n",
    "        return res / k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        maxTotal = total = sum(nums[:k])\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(k, n):\n",
    "            total = total - nums[i - k] + nums[i]\n",
    "            maxTotal = max(maxTotal, total)\n",
    "        \n",
    "        return maxTotal / k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        n = len(nums)\n",
    "        orsum = sum(nums[:k])\n",
    "        maxavg = orsum/k\n",
    "        if n<=k:\n",
    "            return maxavg\n",
    "        for i in range(k,n):\n",
    "            newsum = orsum + nums[i] - nums[i-k]\n",
    "            newavg = newsum/k\n",
    "            if newavg>maxavg:\n",
    "                maxavg = newavg\n",
    "            orsum = newsum\n",
    "        return maxavg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        n=len(nums) \n",
    "        if k>n:return sum(nums)/n\n",
    "        res=(sum(nums[:k]))/k\n",
    "        total=sum(nums[:k])\n",
    "        \n",
    "        for i in range(1,n-k+1):\n",
    "            total=total-nums[i-1]+nums[i+k-1]\n",
    "            average=total/k\n",
    "            res=max(res,average)   #注意是冒号，不是逗号\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        maxi = sum(nums[0:k])\n",
    "        total = maxi\n",
    "        for i in range(k, len(nums)):\n",
    "            total = total - nums[i-k] + nums[i]\n",
    "            maxi = max(maxi, total)\n",
    "        return maxi / k\n",
    "\n",
    "        # maxi = sum(nums[0:k])\n",
    "        # for i in range(k, len(nums)):\n",
    "        #     if nums[i] > nums[i-k]:\n",
    "        #         maxi = max(maxi, sum(nums[i-k+1:i+1]))\n",
    "        # return maxi / k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        sums = 0\n",
    "        max1 = float('-inf')\n",
    "        for i, num in enumerate(nums):\n",
    "            sums += num\n",
    "            if i >= k:\n",
    "                sums -= nums[i-k]\n",
    "            if i >= k -1 :\n",
    "                max1 = max(max1, sums/float(k))\n",
    "        return(max1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        maxTotal = total = sum(nums[:k])\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(k, n):\n",
    "            total = total - nums[i - k] + nums[i]\n",
    "            maxTotal = max(maxTotal, total)\n",
    "        \n",
    "        return maxTotal / k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        n = len(nums)\n",
    "        cusum = [0 for _ in range(n)]\n",
    "        cusum[0] = nums[0]\n",
    "        res = []\n",
    "        for i in range(1, n):\n",
    "            cusum[i] = nums[i] + cusum[i-1]\n",
    "            if i>=k:\n",
    "                res.append((cusum[i]-cusum[i-k])/(1.0*k))\n",
    "        res.append(cusum[k-1]/(1.0*k))\n",
    "        return max(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        res = sum(nums[:k])\n",
    "        total = res\n",
    "        nums = {i: nums[i] for i in range(len(nums))}\n",
    "        for i in range(len(nums)-k):\n",
    "            total = total-nums[i]+nums[i+k]\n",
    "            if total > res:\n",
    "                res = total\n",
    "        return res/k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        res = sum(nums[:k])/k\n",
    "        total = res\n",
    "        nums = {i: nums[i] for i in range(len(nums))}\n",
    "        for i in range(len(nums)-k):\n",
    "            total = (total*k-nums[i]+nums[i+k])/k\n",
    "            if total > res:\n",
    "                res = total\n",
    "            # total = (total*k-nums[i]+nums[i+k])/k\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        if k == 1:\n",
    "            return max(nums)\n",
    "        else:\n",
    "            result = set()\n",
    "            m = sum(nums[0: k])\n",
    "            result.add(m)\n",
    "            for i in range(len(nums) - k):\n",
    "                m += nums[i + k] - nums[i]\n",
    "                result.add(m)\n",
    "        return max(result) / k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        if len(nums) < k: return 0\n",
    "        m = {-1: 0}\n",
    "        for i, n in enumerate(nums):\n",
    "            m[i] = (n + m.get(i-1, 0))\n",
    "        \n",
    "        res = float('-inf')\n",
    "        for i in range(k-1, len(nums)):\n",
    "            # i = k-1 = 3\n",
    "            # i-k = 3-3 = 0\n",
    "            res = max(res, m[i] - m[i-k])\n",
    "        return res / k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        length = len(nums)\n",
    "        max_sum = sum(nums[:k])\n",
    "        curr_sum = max_sum\n",
    "        for start in range(1, length):\n",
    "            end = start + k - 1\n",
    "            if(end == length): break\n",
    "            curr_sum -= nums[start - 1]\n",
    "            curr_sum += nums[end]\n",
    "            max_sum = max(max_sum, curr_sum)\n",
    "        return max_sum / k\n",
    "\n",
    "        ''' 超出时间限制\n",
    "        end = k\n",
    "        for start in range(length):\n",
    "            end = start + k\n",
    "            if(end > length): break\n",
    "            avg = sum(nums[start:end]) / k\n",
    "            max_avg = max(max_avg, avg)\n",
    "        return max_avg\n",
    "        '''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        from fractions import Fraction\n",
    "        ever = sum(nums[:k])\n",
    "\n",
    "        ret = ever / k\n",
    "        # ret = Fraction(ever, k)\n",
    "        for i in range(k, len(nums)):\n",
    "            ever -= nums[i-k]\n",
    "            ever += nums[i]\n",
    "            # ret = max(ret, Fraction(ever, k))\n",
    "            ret = max(ret, ever / k)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        left = 0\n",
    "        right = k-1\n",
    "        max_arvs = []\n",
    "        while right < len(nums):\n",
    "            if left == 0:\n",
    "                arv = sum(nums[left: right+1])/k\n",
    "                max_arvs.append(arv)\n",
    "            else:\n",
    "                arv += (nums[right] - nums[left-1]) / k\n",
    "                if nums[right] > nums[left-1]:\n",
    "                    max_arvs.append(arv)\n",
    "\n",
    "            left += 1\n",
    "            right += 1\n",
    "        return max(max_arvs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        ave=sum(nums[:k])\n",
    "        tmp=ave\n",
    "        for i in range(len(nums)-k):\n",
    "            tmp=tmp-nums[i]+nums[i+k]\n",
    "            if tmp>ave:\n",
    "                ave=tmp\n",
    "        return ave*1.0/k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        maxTotal = total = sum(nums[:k])\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(k, n):\n",
    "            total = total - nums[i - k] + nums[i]\n",
    "            maxTotal = max(maxTotal, total)\n",
    "        \n",
    "        return maxTotal / k\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        # 窗口\n",
    "        ans = -math.inf\n",
    "        count = 0\n",
    "        for i, j in enumerate(nums):\n",
    "            count += j\n",
    "            if i+1 >= k:\n",
    "                ans = max(ans, count)\n",
    "                count -= nums[i+1-k]\n",
    "        return ans/k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        # 先算第一个k窗口内的和，每次循环一位时减去i-k元素的值，加上i元素的值\n",
    "        cnt = 0\n",
    "        for i in range(k):\n",
    "            cnt += nums[i]\n",
    "        avgmax = cnt / k \n",
    "        for i in range(k , len(nums)):\n",
    "            cnt = cnt - nums[i-k] + nums[i]\n",
    "            avgmax = max(avgmax , cnt / k)\n",
    "        return avgmax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        # 用滑动窗口\n",
    "        # 定义需要维护的变量\n",
    "        maxx = float('-inf')\n",
    "        # 定义 start \n",
    "        start = 0\n",
    "        summ = 0\n",
    "        for end in range(len(nums)):\n",
    "            summ += nums[end]\n",
    "            if end - start + 1 == k:\n",
    "                # 更新\n",
    "                maxx = max(summ, maxx)\n",
    "            if end >= k-1:\n",
    "                summ -= nums[start]\n",
    "                start += 1\n",
    "        return maxx/k            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        sum_, avg_max = 0, -math.inf\n",
    "        start = 0\n",
    "        for end in range(len(nums)):\n",
    "            sum_ += nums[end]\n",
    "            if end - start + 1 == k:\n",
    "                avg_max = max(avg_max, sum_ / k)\n",
    "            if end >= k -1:\n",
    "                sum_ -= nums[start]\n",
    "                start += 1\n",
    "        return avg_max "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        maxSum = curSum = sum(nums[:k])\n",
    "\n",
    "        for r in range(k, len(nums)):\n",
    "            curSum = curSum - nums[r-k] + nums[r]\n",
    "            maxSum = max(maxSum, curSum)\n",
    "        \n",
    "        return maxSum / k\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        sums = 0\n",
    "        left = 0 \n",
    "        maxavg = -math.inf\n",
    "        for right in range(len(nums)):\n",
    "            sums += nums[right] \n",
    "            if right - left + 1 == k:\n",
    "                maxavg = max(maxavg, sums / k)\n",
    "\n",
    "            if right >= k-1:\n",
    "                sums -= nums[left] \n",
    "                left +=1 \n",
    "\n",
    "        return maxavg"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
